package com.twopointer;

import java.util.Arrays;

/**
 * [3, 4, 6, 7]
 */
public class TriangleCount {
    public static void main(String[] args) {
        int[] S = {3, 4, 6, 7};
        System.out.println(triangleCount(S));
    }

    public static int triangleCount(int[] S) {
        if (S == null || S.length < 3) return 0;
        Arrays.sort(S);

        int total = 0;
        for (int k = S.length - 1; k >= 2; k--) {
            int start = 0;
            int end = k - 1;

            while (start < end) {
                if (S[start] + S[end] > S[k]) {
                    total += end - start;
                    end--;
                } else {
                    start++;
                }
            }
        }
        return total;
    }
}
